The distribution of data flow among multiple data paths between nodes in a communication network is an important consideration in the efficient operation of a communication network. When multiple data link paths exist between two network nodes, proper allocation of the data among the data paths reduces the potential of overloading a single data link or node, and increases the utilization of the network.
FIG. 1 illustrates a typical network configuration containing three primary nodes: A 100, B 110 and C 120. Numerous intermediate nodes are interconnected between nodes the primary nodes. Data flowing between primary nodes A and B may be distributed so as to pass through any one of a group of intermediate nodes. For example, intermediate nodes D 130 and E 140 may be used to route data from node A 100 to node B 110. Similarly, intermediate nodes F 150, G 160 and H 170 may be used to route data from primary node A 100 to primary node C 120, and intermediate node I 180 may be used to route data from primary node C 120 to primary node B 110. Thus, data that must be transmitted from primary node A 100 to primary node B 110 may be allocated to various combinations of paths, such as A-E-B, A-D-B, A-D-E-B, A-E-D-B, A-C-B, A-F-C-B, A-F-G-C-B, etc. These paths to which data may be allocated represent a single commodity flow.
Methods of determining the allocation of a commodity flow in a Point-to-Point network are known in the art. Usually, linear programming techniques are used to determine the allocation of data flow among various network data paths. For example, one such method which determines multi-commodity flow for a price distributed among the data links is disclosed by N. Garg and J. Konemann, in an article entitled “Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems,” Proceedings of the 39th Annual Symposium on Foundations of Comp. Science, pages 300–309, Palo Alto, Calif., November 1998, IEEE. Methods for determining commodity flow, however, are typically computationally intensive, requiring significant time to compute and determine a single distribution allocation. Accordingly, there is a need to provide a method to quickly determine a new allocation distribution which can be readily adapted to a computer and which is particularly adapted to situations when parameters that influence data flow allocation are changeable.